package zuoshen_video;

import java.util.*;

import org.junit.Test;

import utils.ArrayGenerator;
public class MatrixProblem {

    //1.旋转打印矩阵
    public List<Integer> getRotateMatrix(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        int li = 0, lj = 0, ri = m - 1, rj = n - 1; //最外层的左上点以及右下点
        List<Integer> res = new ArrayList<>();
        while (li <= ri && lj <= rj) { //当行列有一个发生变卦，证明遍历结束
            //处理单行或者单列的情况
            if (li == ri) {
                //单行
                for (int i = lj; i <= rj; i++) {
                    res.add(matrix[li][i]);
                }
            } else if (lj == rj) {
                //单列
                for (int i = li; i <= ri; i++) {
                    res.add(matrix[i][lj]);
                }
            } else {
                //正常矩阵情况，顺时针打印
                for (int i = lj; i < rj; i++) res.add(matrix[li][i]);
                for (int i = li; i < ri; i++) res.add(matrix[i][rj]);
                for (int i = rj; i > lj; i--) res.add(matrix[ri][i]);
                for (int i = ri; i > li; i--) res.add(matrix[i][lj]);
            }
            //向中间进一格
            li++;
            lj++;
            ri--;
            rj--;
        }
        return res;
    }

    //90度旋转图像【其实长方形矩形也可以旋转，但是会创建额外数组，本题失去意义】
    class Solution {
        public void rotate(int[][] matrix) {
            int m = matrix.length - 1;
            int li = 0, lj = 0, ri = m, rj = m; //最外层的左上点以及右下点
            while (li <= ri && lj <= rj) {
                for (int i = lj; i < rj; i++) {
                    int temp = matrix[li][i];
                    matrix[li][i] = matrix[m - i][li];
                    matrix[m - i][li] = matrix[m - li][m - i];
                    matrix[m - li][m - i] = matrix[i][m - li];
                    matrix[i][m - li] = temp;
                }
                li++;
                lj++;
                ri--;
                rj--;
            }
        }
    }

    //之字形打印矩阵
    //不再从矩阵左上与右下考虑，而是从每次的打印路径两端考虑
    public List<Integer> printMatrixZagzig(int[][] matrix) {
        int li = 0, lj = 0, ri = 0, rj = 0, m = matrix.length, n = matrix[0].length;
        boolean flag = true; //为true表示从左下打印到右上
        List<Integer> res = new ArrayList<>();

        while (ri < m) { //右边点一直在矩形范围内
            if (flag) {
                //左下打印到右上
                int i = li, j = lj;
                while (i >= ri && j <= rj) {
                    res.add(matrix[i--][j++]);
                }
            } else {
                //右上打印到左下
                int i = ri, j = rj;
                while (i <= li && j >= lj) {
                    res.add(matrix[i++][j--]);
                }
            }

            //端点与flag的更新，需要注意矩阵左下和右下拐角时的拐弯
            lj = li < m - 1 ? lj : lj + 1; //当li到达最下边的拐角之后，lj才开始自增
            li = li == m - 1? m - 1 : li + 1;
            ri = rj < n - 1 ? ri : ri + 1;
            rj = rj == n - 1 ? n - 1 : rj + 1;
            flag = !flag;
        }
        return res;
    }

    @Test
    public void test() {
        int[][] matrix = new int[5][];
        matrix[0] = ArrayGenerator.getArray(100, 5);
        matrix[1] = ArrayGenerator.getArray(100, 5);
        matrix[2] = ArrayGenerator.getArray(100, 5);
        matrix[3] = ArrayGenerator.getArray(100, 5);
        matrix[4] = ArrayGenerator.getArray(100, 5);
        // int[][] matrix = new int[3][];
        // matrix[0] = ArrayGenerator.getArray(100, 3);
        // matrix[1] = ArrayGenerator.getArray(100, 3);
        // matrix[2] = ArrayGenerator.getArray(100, 3);
        for (int i = 0; i < matrix.length; i++) {
            System.out.println(Arrays.toString(matrix[i]));
        }
        System.out.println("===============================");
        // System.out.println(getRotateMatrix(matrix));
        // new Solution().rotate(matrix);
        // for (int i = 0; i < matrix.length; i++) {
        //     System.out.println(Arrays.toString(matrix[i]));
        // }
        System.out.println(printMatrixZagzig(matrix));
    }
    
}
